package lanQiaoBei.数学知识.欧拉函数;

import java.io.*;
import java.util.*;

/*欧拉函数（N*(1-1/p1)*(1-1/p2)*....）(快速求出1-N中与N互质的个数)
给定 n 个正整数 ai，请你求出每个数的欧拉函数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围

1≤n≤100,
1≤ai≤2×1e9

输入样例：

3
3
6
8

输出样例：

2
2
4
* */
public class P1 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final static int N = 110;

    static void scan() throws Exception {

    }

    public static void main(String[] args) throws Exception {
        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            int x = Integer.parseInt(br.readLine()), res = x;
            for (int i = 2; i <= x / i; i++) {
                if (x % i == 0) {
                    while (x % i == 0) {
                        x /= i;
                    }
                    res = res * (i - 1) / i;
                }
            }
            if (x > 1) res = res * (x - 1) / x;
            System.out.println(res);
        }
    }
}
